home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-01-14  |  1.8 KB  |  93 lines
  1. #include "voronoi.h"
  2.  
  3. PQinsert(he, v, offset)
  4. struct Halfedge *he;
  5. struct Site *v;
  6. float     offset;
  7. {
  8.     struct Halfedge *last, *next;
  9.  
  10.     he->vertex = v;
  11.     ref(v);
  12.     he->ystar = v->coord.y + offset;
  13.     last = &PQhash[PQbucket(he)];
  14.     while ((next = last->PQnext) != (struct Halfedge *) NULL &&
  15.       (he->ystar  > next->ystar  ||
  16.     (he->ystar == next->ystar && v->coord.x > next->vertex->coord.x))) {
  17.     last = next;
  18.     }
  19.     he->PQnext = last->PQnext; 
  20.     last->PQnext = he;
  21.     PQcount += 1;
  22. }
  23.  
  24. PQdelete(he)
  25. struct Halfedge *he;
  26. {
  27.     struct Halfedge *last;
  28.  
  29.     if(he-> vertex != (struct Site *) NULL) {    
  30.     last = &PQhash[PQbucket(he)];
  31.     while (last->PQnext != he) 
  32.         last = last->PQnext;
  33.     last->PQnext = he->PQnext;
  34.     PQcount -= 1;
  35.     deref(he->vertex);
  36.     he->vertex = (struct Site *) NULL;
  37.     }
  38. }
  39.  
  40. int PQbucket(he)
  41. struct Halfedge *he;
  42. {
  43.     int bucket;
  44.  
  45.     bucket = (he->ystar - ymin)/deltay * PQhashsize;
  46.     if (bucket<0) 
  47.     bucket = 0;
  48.     if (bucket>=PQhashsize) 
  49.     bucket = PQhashsize-1 ;
  50.     if (bucket < PQmin) 
  51.     PQmin = bucket;
  52.     return(bucket);
  53. }
  54.  
  55. int PQempty()
  56. {
  57.     return(PQcount==0);
  58. }
  59.  
  60. struct Point PQ_min()
  61. {
  62.     struct Point answer;
  63.  
  64.     while(PQhash[PQmin].PQnext == (struct Halfedge *)NULL) 
  65.     PQmin += 1;
  66.     answer.x = PQhash[PQmin].PQnext->vertex->coord.x;
  67.     answer.y = PQhash[PQmin].PQnext->ystar;
  68.     return (answer);
  69. }
  70.  
  71. struct Halfedge *PQextractmin()
  72. {
  73.     struct Halfedge *curr;
  74.  
  75.     curr = PQhash[PQmin].PQnext;
  76.     PQhash[PQmin].PQnext = curr->PQnext;
  77.     PQcount -= 1;
  78.     return(curr);
  79. }
  80.  
  81. PQinitialize()
  82. {
  83.     int i; 
  84.  
  85.     PQcount = 0;
  86.     PQmin = 0;
  87.     PQhashsize = 4 * sqrt_nsites;
  88.     PQhash = (struct Halfedge *) myalloc(PQhashsize * sizeof (struct Halfedge));
  89.     for(i=0; i<PQhashsize; i+=1) 
  90.     PQhash[i].PQnext = (struct Halfedge *)NULL;
  91. }
  92.  
  93.